A computer application being executed by a computing device typically provides a page to a device for printing and/or display in the form of a description of the page. The description is provided to device driver software of the device in a page description language (PDL), such as Adobe® PDF or Hewlett-Packard® PCL. The PDL document provides descriptions of objects to be rendered onto the page, as opposed to a raster image of the page to be reproduced, for example by printing onto a hard copy medium such as paper, or display upon a video display device. Equivalently, a set of descriptions of graphic objects may be provided in function calls to a graphics interface, such as the Graphical Device Interface (GDI) in the Microsoft Windows™ operating system, or X-11 in the Unix™ operating system, as used in many computing devices. The page is typically rendered for printing and/or display by an object-based graphics system, also known as a Raster Image Processor (RIP).
A PDL-based printer must be able to reliably handle PDL input of high complexity. Objects stored in PDL graphics formats are typically presented to the RIP in z-order, where objects of higher z-order are ‘painted’ on top of objects which have a lower z-order. Marking engines in printing devices however must operate in y-order, where output pixels are transferred to the output medium in raster order down the page. Thus, a universal problem in all PDL printing applications is the need to convert the input z-ordered object graphics to output y-ordered rendered graphics. Printing of the input PDL graphics cannot commence until all input PDL objects have been received by the RIP.
It is not always possible to interpret highly complex PDL input in entirety prior to pixel generation in view of the typically limited memory and processor resources available in a printing system. Consequently, several methods have been utilized in the prior art to enable PDL printers to process highly complex input PDL jobs prior to final pixel generation.
One approach to render a complex graphical input is to process pixels in a pixel sequential manner. The pixel sequential class of rendering algorithms performs pixel generation operations once for all page pixels, rather than once per each object covering a given pixel. Such an approach is beneficial, especially in the case of many overlapping objects on the page. Also, large frame stores are not required in pixel sequential rendering. However, pixel sequential rendering often requires a larger amount of working memory, because a state of rasterization process must be kept for all active objects.
The amount of memory that the rasterization process can use is limited. In some systems, the limiting factor is how much memory is available. If the amount of memory available is less than the amount of memory required for rasterization, the rasterization process cannot succeed, i.e. the print job fails. In other systems, the available amount of fast memory cache is the limiting factor. If a sufficient amount of fast memory cache is not available, the rasterization process may have to use slow memory for storing working data resulting in a significant performance degradation.
One known method involves dividing a complex PDL input into batches of foreground objects which are scan-converted and composited onto a background bitmap. The batches of objects are often referred to as z-layers since the objects are grouped in z-order. Often, the size of the z-layers is chosen to optimise the processing efficiency of the RIP. The resultant bitmap may be compressed and be used as the background bitmap for subsequent foreground object batches. The increased processing of compressed bitmaps impacts on the overall performance as each bitmap has to be decompressed before compositing. Furthermore, compression artefacts are also likely to be introduced to the compositing operation, and will consequently degrade the quality of the final output. Even if a lossless compression technique is used, the method requires a large amount of memory to store the background bitmap. Other similar known methods divide the page into strips and batch objects according to the strips. Methods dividing the page into strips suffer similar disadvantages to dividing PDL input batches into foreground objects. In an embedded printing application, resource constraints magnify the performance and quality disadvantages.
Other known methods convert a batch of consecutive PDL input objects to an intermediate format representation representing a format between a page description language (PDL) and a bitmap, such as a fillmap or planar map. The arrangements described use a fillmap example. FIG. 1 is a schematic flow diagram that demonstrates the top-level processing of the fillmap method. The batch fillmaps are merged into a merged fillmap to reduce memory usage. Due to the lossless and compact nature of fillmaps, the merged fillmap will often lead to a saving of system resources while preserving the original quality of the PDL data. The final merged fillmap presents the final graphic layout for the page, and hence is often referred to as the page fillmap or the background fillmap. Once the merged fillmap contains all input graphics for the page, the fillmap can be rasterised to pixels, and sent to the marking engine for printing. The method overcomes the quality and performance degradation that is seen in other bitmap based approaches.
Although the method using fillmaps typically works well for the majority of test cases, resources may still be exhausted during the generation of these batch fillmaps. In low-end printing devices, severe resource constraints may result in inadequate memory being available for working memory or for storing the generated batch fillmaps. Ultimately, there may not be sufficient resources for storing the merged fillmap for the page.
A typical response to resource shortage is to rasterise the incomplete merged fillmap to a background bitmap, and lossily compress the background bitmap. The response requires that sufficient memory has been ‘reserved’ to perform this rasterization as well as storing the pixel bitmap produced. However, the merged fillmap data can typically be deleted as the output pixels are generated, and this pixel data can also be compressed upon generation, freeing memory.
Another known technique in many printing systems for addressing resource constraints is to temporarily store intermediate data to an external hard disk. The technique is common in printer drivers, and in office embedded printers where a hard disk is present. However, low-end printers such has those common in the consumer market typically do not include a hard disk drive.
Alternative approaches calculate complexity of input data to estimate the amount of memory required to render a display list. The input is layered when the memory estimate reaches a given threshold. The generated layers are then rendered to the background image. Because it is difficult to make an accurate estimation, or making such an estimate would have been prohibitively expensive, the fixed memory is allocated with a large tolerance for estimation inaccuracy to ensure that rendering to pixels succeeds. As such, the working memory is almost always underutilised, especially for small to medium complexity jobs. The generated layers are typically smaller than they otherwise may be thereby creating significant overhead of merging of many layers into the final raster representation, which badly affects performance of pixel sequential methods. Furthermore, no recovery is provided from failure to rasterize a display list due to lack of available memory, which can happen even with a conservative approach to memory estimate.
There are methods of calculating page complexity by decomposing all drawing commands to linear vectors, and spatially splitting the input data if the number of vectors that cross the scanlines exceeds a given predetermined threshold. Such methods may reduce working memory (at the expense of making expensive decomposition to the linear vectors upfront). However, the number of scanline crossings still cannot guarantee that the rasterization job succeeds in the fixed amount of memory.
Several spatial only division methods subdivide a tile into a plurality of sub-tiles until a sub-tile fits a pre-allocated memory buffer. However, when the input job has very fine detail and many objects cover a small area, spatial division of the page (even recursively) may not help reduce the amount of data required by a pixel-sequential renderer. For example, after subdivision, each subregion may bear the same, or substantially the same, amount of contributing objects. Thus, the working memory may not be significantly reduced, especially when the input objects are processed by a pixel sequential renderer.
Other methods utilise spatial subdivision in addition to layering to reduce total system working memory usage. For example, a display list can be stored as a “macro-tile” list for objects falling entirely within a macro-tile and “global” list for large objects covering two or more macro-tiles. Rendering starts when a memory threshold (e.g. 70%) is reached. However, the threshold is only a reserve, therefore, in some cases subsequent rasterization of a display may fail. While for display rendering occasional failure to render single frames may be tolerable, in print rendering all jobs must be successfully rasterized otherwise a user would receive incorrect print output.
Another approach improves the performance of the pixel sequential rendering system by finding a balance between making use of computing resources (including memory resources) and minimising the processing time. Such an approach may find an optimal memory use in some cases but is computationally expensive and does not guarantee that layers would be successfully converted to an intermediate format representation.
In an attempt to overcome the problems described above, PDL rendering systems intended for low-end embedded printers are typically designed to operate using as little memory as possible. However, most pages to be printed are of moderate or low complexity and size. As a result, the performance of such a low-end printing device may be unnecessarily reduced for such pages. Also, known rendering systems typically only react to resource conditions once they occur, and do not anticipate impending resource shortages.
Thus there is a need to provide a system and a method for processing a print job that can utilise system memory efficiently and facilitate successful conversion of a majority of print jobs to an intermediate format representation within a fixed amount of memory.